#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
using namespace std;

#if 0
int strStr(string haystack, string needle) {
	for (int i = 0; i<haystack.size(); i++)
	{
		int j = 0;
		if (haystack[i] == needle[j])
		{
			int n = i;
			while (j < needle.size() && haystack[n] == needle[j])
			{
				n++, j++;
			}
			if (n - i == needle.size())
			{
				return i;
			}
		}
	}
	return -1;
}

vector<int> BuildNext(string& needle)
{
	vector<int> next;
	int i = 1, prefix = 0;
	next.push_back(0);
	while (i<needle.size())
	{
		if (needle[i] == needle[prefix])
		{
			prefix++;
			next.push_back(prefix);
			i++;
		}
		else
		{
			if (prefix == 0)
			{
				next.push_back(prefix);
				i++;
			}
			else
			{
				prefix = next[prefix - 1];
			}
		}
	}
	return next;
}
int strStr(string haystack, string needle) {
	vector<int> next = BuildNext(needle);
	int i = 0, j = 0;
	while (i < haystack.size())
	{
		if (haystack[i] == needle[j])
		{
			i++,j++;
		}
		else if (j>0)
		{
			j = next[j - 1];
		}
		else
		{
			i++;
		}
		if (j == needle.size())
		{
			return i - j;
		}
	}
	return -1;
}
int main()
{
	string s1 = "aaaaaaaab";
	string s2 = "aab";
	cout << strStr(s1, s2) << endl;
	return 0;
}

bool repeatedSubstringPattern(string s) {
	for (int i = 1; i<s.size(); i++)
	{
		string clone = s.substr(i) + s.substr(0, i);
		if (clone == s)
		{
			return true;
		}
	}
	return false;
}
int main()
{
	cout << repeatedSubstringPattern("abab") << endl;
	return 0;
}

vector<int> BuildNext(string& needle)
{
	vector<int> next;
	int i = 1, prefix = 0;
	next.push_back(0);
	while (i<needle.size())
	{
		if (needle[i] == needle[prefix])
		{
			prefix++;
			next.push_back(prefix);
			i++;
		}
		else
		{
			if (prefix == 0)
			{
				next.push_back(prefix);
				i++;
			}
			else
			{
				prefix = next[prefix - 1];
			}
		}
	}
	return next;
}
bool repeatedSubstringPattern(string s) {
	vector<int> next = BuildNext(s);
	int len = next.size()-1;
	if (next[len] != 0 && (s.size() % (len + 1 - next[len]) == 0))
	{
		return true;
	}
	return -1;
}
int main()
{
	cout << repeatedSubstringPattern("abcabcabcabc") << endl;
	return 0;
}
#endif

int Add() throw();

template<class T>
inline T Add(T a, T b)
{
	return a + b;
}
int main()
{
	cout << Add(3, 4) << endl;
	return 0;
}